#define _CRT_SECURE_NO_DEPRECATE
#include <cstdio>
#include <fcntl.h> // for _O_BINARY
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <cmath>
#include "ext_rational.h"

using namespace std;

#ifndef __GNUC__
typedef __int64 i64;
#else
typedef long long i64;
#endif

// Real constants

const int LITTLE_MEMORY = 1<<27; // Assuming we always have 128M
const int QUEUE_MEMORY_STEP = 1<<27;
const int DFA_MEMORY_STEP = 1<<22;

const int MAX_ALPH_SIZE = 16;
const int MAX_WORD_LENGTH = 10000;
const int MINITER = 25;


// Binary Encoding Stuff
bool use_long_mask;
const char LONG_MASK = 0x0F;
const char SHORT_MASK = 0x03;


const char swapfile_name[30] = "zzzedges.txt";
FILE * swapfile;
const int SWAP_BUFFER_SIZE = 1 << 14;
int swap_buffer[SWAP_BUFFER_SIZE]; // 65536 bytes

// Read from ini-file
// They are either taken from ini-file or defined here

bool auto_queue_size = true;
bool auto_dfa_size = true;
int QUEUE_SIZE; // 1 byte is used for storing 2 letters
int DFA_SIZE; // less than 2^28 !!!!

int MAXITER = 5000;

// Modifiers
bool OUTPUT_PROGRESS = false; // writes additional data
bool USE_ORACLE = false; // true - Algo1, false - Algo1Q
bool ADD_LOOPS = false; // if we add loops, it makes algorithm work slower, but DFA is always primitive

int GEN_EDGE_LIST = -1; // replaces DFA with edge list, sometimes work faster
// 0 - not use, 1 - use, -1 - auto

bool USE_SWAP_FILE = false; // significantly slower, but saves memory

// Debug purposes only
#define OUTPUT_ANTIDICTIONARY false
#define OUTPUT_DFA false

// The values are taken from input
int ALPH_SIZE;
int ROOT_LENGTH;
ext_rational beta;
double delta;

// ANTIDICTIONARY CONSTRUCTION

i64 max_words_queue_size;
char * words_queue;
i64 qbeg, qend;
char bij[MAX_ALPH_SIZE];

int total, words_num;
int * dfa;

// Determines if queue size is more important than dfa size
int queue_more_important(){
  if (ALPH_SIZE <= 2) return 0;
  return (beta < ext_rational(ALPH_SIZE-1, ALPH_SIZE-2, 1));
}

void set_queue_size(){
  double max_size = ROOT_LENGTH * pow((double)ALPH_SIZE, (double)ROOT_LENGTH);
  if (sizeof(char) * max_size < LITTLE_MEMORY){
    QUEUE_SIZE = (int)max_size + 1;
  }
  else{
    QUEUE_SIZE = QUEUE_MEMORY_STEP;
    while (1){
      try{
        words_queue = new char [QUEUE_SIZE + QUEUE_MEMORY_STEP];
        delete[] words_queue;
        QUEUE_SIZE += QUEUE_MEMORY_STEP;
      }
      catch(...){
        break;
      }
      /*if (words_queue != NULL){
        delete[] words_queue;
        QUEUE_SIZE += QUEUE_MEMORY_STEP;
      }
      else break;*/
    }
    QUEUE_SIZE >>= 1;
  }
  words_queue = new char [QUEUE_SIZE];
}

void set_dfa_size(){
  double max_size = ROOT_LENGTH * pow((double)ALPH_SIZE, (double)ROOT_LENGTH);
  if (sizeof(int) * max_size * ALPH_SIZE < LITTLE_MEMORY){
    DFA_SIZE = (int)max_size + 1;
  }
  else{
    DFA_SIZE = DFA_MEMORY_STEP;
    while (1){
      try{
        dfa = new int [(DFA_SIZE + DFA_MEMORY_STEP) * ALPH_SIZE];
        delete[] dfa;
        DFA_SIZE += DFA_MEMORY_STEP;
      }
      catch(...){
        break;
      }
    }
    DFA_SIZE >>= 1;
  }
  dfa = new int [DFA_SIZE * ALPH_SIZE];
}

void init(){
  if (auto_queue_size == false){
    words_queue = new char [QUEUE_SIZE];
  }
  if (auto_dfa_size == false){
    dfa = new int [DFA_SIZE * ALPH_SIZE];
  }
  
  if (queue_more_important()){
    if (auto_queue_size) set_queue_size();
    if (auto_dfa_size) set_dfa_size();
  }
  else{
    if (auto_dfa_size) set_dfa_size();
    if (auto_queue_size) set_queue_size();
  }

  if (OUTPUT_PROGRESS){
    if (auto_queue_size) printf("Amount of memory allocated for queue = %d bytes\n", sizeof(char)*QUEUE_SIZE);
    if (auto_dfa_size) printf("Amount of memory allocated for DFA = %d bytes\n", sizeof(int)*DFA_SIZE*ALPH_SIZE);
  }

  use_long_mask = (ALPH_SIZE > 4);
  
  total = 1;
  memset(dfa, 0, sizeof(int) * DFA_SIZE * ALPH_SIZE);
  qbeg = 0;
  qend = 0;
}

inline void inc_queue_index(long long &i){
  i++;
  if (use_long_mask){
    if ((i>>1) >= QUEUE_SIZE){
      i = 0;
    }
  }
  else{
    if ((i>>2) >= QUEUE_SIZE){
      i = 0;
    }
  }
}

inline void push_symbol(char ch){
  ch -= 'a';
  if (use_long_mask){
    int mod = (int)(qend&1);
    words_queue[qend>>1] &= ~(LONG_MASK << (4*mod));
    words_queue[qend>>1] |= (ch << (4*mod));
  }
  else{
    int mod = (int)(qend&3);
    words_queue[qend>>2] &= ~(SHORT_MASK << (2*mod));
    words_queue[qend>>2] |= (ch << (2*mod));
  }
  inc_queue_index(qend);
  if (qbeg == qend){
    printf("ERROR! Insufficient words queue size!\n");
    exit(1);
  }
  if (OUTPUT_PROGRESS){
    i64 zsize = qend - qbeg;
    if (zsize < 0){
      if (use_long_mask) zsize += 2*QUEUE_SIZE;
      else zsize += 4*QUEUE_SIZE;
    }
    if (zsize > max_words_queue_size){
      max_words_queue_size = zsize;
    }
  }
}

/*inline void push_marker(){
  push_symbol('a' + MASK);
}*/

inline void push_marker(long long &mpos){
  mpos = qend;
  push_symbol('a'); // not important which symbol to put
}

inline char qbeg_symbol(){
  //return (qbeg&1) ? (((words_queue[qbeg>>1]) & (MASK << 4)) >> 4) : (words_queue[qbeg>>1] & MASK);
  if (use_long_mask){
    int mod = (int)(qbeg&1);
    return (words_queue[qbeg>>1] & (LONG_MASK << (4*mod))) >> (4*mod);
  }
  else{
    int mod = (int)(qbeg&3);
    return (words_queue[qbeg>>2] & (SHORT_MASK << (2*mod))) >> (2*mod);
  }
}

inline void push_word(const char * word){
  int i;
  for (i=0; word[i]; i++){
    push_symbol(word[i]);
  }
}

// Checks if some prefix of the word in buff is forbidden,
// dir=1 if the word is read normally or dir=-1 if it is read backwards
bool forbidden(const char * buff, int len, char dir){
  int cv = 1, i, sp = 0, fp = len, cur = 0;
  if (dir < 0){
    sp = len-1;
    fp = -1;
  }
  memset(bij, 0, sizeof(char)*ALPH_SIZE);
  for (i=sp; i!=fp; i+=dir){
    if (!bij[buff[i]-'a']){
      bij[buff[i]-'a'] = 'a' + cur;
      cur++;
    }
    int c = bij[buff[i]-'a'] - 'a';
    int zv = dfa[cv * ALPH_SIZE + c];
    if (!zv) return false;
    if (zv < 0) return true;
    cv = zv;
  }
  return false;
}

// Adds the word to automaton
void add_word(const char * word){
  int cv = 1, i;
  words_num++;
  for (i=0; word[i+1]; i++){
    int c = word[i]-'a';
    if (!dfa[cv*ALPH_SIZE + c]){
      total++;
      if (total >= DFA_SIZE){
        printf("ERROR! Insufficient DFA size!\n");
        exit(1);
      }
      dfa[cv*ALPH_SIZE + c] = total;
    }
    cv = dfa[cv*ALPH_SIZE + c];
  }
  dfa[cv*ALPH_SIZE + word[i]-'a'] = -1;
}

char thword[MAX_WORD_LENGTH + 1];

// Hadles root stored in cword and adds forbidden word constructed from it if necessary
// Returns the number of first bad prefix
int handle_word(const char* cword, int clen){
  char maxlet = 'a';
  int i;
  for (i=0; i<clen; i++){
    thword[i] = cword[i];
    if (thword[i] > maxlet){
      maxlet = thword[i];
    }
  }
  int blen = clen, cpos = 0;
  while (ext_rational(blen, clen, 0) < beta){
    thword[blen++] = thword[cpos];
    //cpos = (cpos + 1) % clen;
    cpos++;
    if (cpos >= clen) cpos = 0;
  }

  thword[blen] = 0;

  if (blen > MAX_WORD_LENGTH){
    printf("Too small maximal length of forbidden word!\n");
    exit(1);
  }
  for (i=clen+1; i<blen; i++){
    if (forbidden(thword, i, -1)){
      return i;
    }
  }
  if (forbidden(thword+1, blen-1, -1) || forbidden(thword, blen, 1)){
    return blen;
  }
  add_word(thword);
  return 0;
}

// Main trie build procedure
void build_antidictionary(){
  long long marker_pos;
  push_marker(marker_pos); // sets marker_pos to 0
  push_symbol('a');
  int i;
  int clen = 0;
  char bad_word[MAX_WORD_LENGTH + 1];
  char dont_put_a;
  while (qbeg != qend){
    //if (qbeg_symbol() == MASK){
    if (qbeg == marker_pos){
      if (clen < ROOT_LENGTH){
        clen++;
        push_marker(marker_pos);
        inc_queue_index(qbeg);
        continue;
      }
      else break;
    }
    
    // there is a word in the queue starting at qbeg with (length = clen)
    char maxlet = 'a';
    for (i=0; i<clen; i++){
      bad_word[i] = qbeg_symbol() + 'a';
      inc_queue_index(qbeg);
      if (bad_word[i] > maxlet){
        maxlet = bad_word[i];
      }
    }

    int fbad = handle_word(bad_word, clen);
    dont_put_a = (fbad == clen+1);

    if (clen < ROOT_LENGTH){
      char ch;
      for (ch='a'+dont_put_a; ch<=maxlet; ch++){
        bad_word[clen] = ch;
        bad_word[clen+1] = 0;
        if (!forbidden(bad_word, clen+1, -1)){
          if (clen < ROOT_LENGTH - 1) push_word(bad_word);
          else handle_word(bad_word, clen+1);
        }
      }
      if (maxlet-'a'+1 < ALPH_SIZE){
        bad_word[clen] = maxlet+1;
        bad_word[clen+1] = 0;
        if (clen < ROOT_LENGTH - 1) push_word(bad_word);
        else handle_word(bad_word, clen+1);
      }
    }

  }

  delete[] words_queue;

}



// AUTOMATON CONSTRUCTION

//char * last;
//int * lf;
const int LAST_MASK = (15 << 28);
const int LF_MASK = (1<<28) - 1;
int * lf_last;

char * sigma;

int back_pack_mode; // 0 - 4 bits per mask, 1 - 8 bits per mask, 2 - 16 bits per mask
short * back;

int * vert_queue;
int vqbeg, vqend;
int vqsize; // always a perfect power of 2

inline void push_vertex(int x){
  vert_queue[vqend] = x;
  vqend = (vqend + 1) & (vqsize - 1);
}

int SIGMA_LEN;

inline char get_sval(char * s, int c){
  return (c & 1) ? ((s[c>>1] & (LONG_MASK << 4)) >> 4) : (s[(c>>1)] & LONG_MASK);
}

inline void set_sval(char * s, int c, char d){
  if (c & 1){
    s[c >> 1] &= LONG_MASK;
    s[c >> 1] |= (d << 4);
  }
  else{
    s[c >> 1] &= (LONG_MASK << 4);
    s[c >> 1] |= d;
  }
}

void make_permut(char* p1, char* p2){
  int i;
  for (i=0; i<ALPH_SIZE; i++){
    if (get_sval(p1, i) != LONG_MASK){
      set_sval(p1, i, get_sval(p2, get_sval(p1, i)));
    }
  }
}

inline char get_sigma(int v, int c){
  return get_sval(sigma + v*SIGMA_LEN, c);
}

inline void set_sigma(int v, int c, char d){
  set_sval(sigma + v*SIGMA_LEN, c, d);
}

inline void set_last(int v, char c){
 lf_last[v] &= ~LAST_MASK;
 lf_last[v] |= ((int)(c) << 28);
}

inline void set_lf(int v, int clf){
  lf_last[v] &= ~LF_MASK;
  lf_last[v] |= clf;
}

inline char get_last(int v){
  char z = (((lf_last[v] & LAST_MASK) >> 28) & LONG_MASK);
  return (z == 15) ? -1 : z;
}

inline int get_lf(int v){
  return lf_last[v] & LF_MASK;
}

inline void set_back(int v, int c){
  if (back_pack_mode == 0){
    int mod = v&3;
    back[v>>2] |= (1 << (4*mod + c));
  }
  else if (back_pack_mode == 1){
    int mod = v&1;
    back[v>>1] |= (1 << (8*mod + c));
  }
  else{
    back[v] |= (1 << c);
  }
}

inline bool is_back(int v, int c){
  if (back_pack_mode == 0){
    int mod = v&3;
    return (back[v>>2] & (1 << (4*mod + c))) > 0;
  }
  else if (back_pack_mode == 1){
    int mod = v&1;
    return (back[v>>1] & (1 << (8*mod + c))) > 0;
  }
  else{
    return (back[v]  & (1 << c)) > 0;
  }
}

void cnt_vertex(int v){
  int c;
  char * zsigma = new char [SIGMA_LEN];
  //char clast = last[v];
  char clast = get_last(v);
  for (c=0; c<=clast+1; c++){
    if (c >= ALPH_SIZE) break;
    if (!dfa[v*ALPH_SIZE + c]){
      char d = get_sigma(v, c);
      if (d == LONG_MASK){
        //d = last[lf[v]] + 1;
        d = get_last(get_lf(v)) + 1;
      }
      //dfa[v*ALPH_SIZE + c] = dfa[lf[v]*ALPH_SIZE + d];
      dfa[v*ALPH_SIZE + c] = dfa[get_lf(v)*ALPH_SIZE + d];
      //back[v] |= (1 << c);
      set_back(v, c);
    }
    else{
      int u = dfa[v*ALPH_SIZE + c];
      if (u < 0){
        dfa[v*ALPH_SIZE + c] = 0;
        continue;
      }
      push_vertex(u);
      //last[u] = (c > clast) ? c : clast;
      set_last(u, (c > clast) ? c : clast);
      memcpy(sigma + u*SIGMA_LEN, sigma + v*SIGMA_LEN, sizeof(char)*SIGMA_LEN);
      char d = get_sigma(v, c);
      if (d == LONG_MASK){
        //d = last[lf[v]] + 1;
        d = get_last(get_lf(v)) + 1;
        set_sigma(u, c, d);
      }
      //lf[u] = dfa[lf[v]*ALPH_SIZE + d];
      set_lf(u, dfa[get_lf(v)*ALPH_SIZE + d]);
      //int zv = lf[v];
      int zv = get_lf(v);
      //while (back[zv] & (1 << get_sigma(u, c))){
      while (is_back(zv, get_sigma(u, c))){
        memcpy(zsigma, sigma + zv*SIGMA_LEN, sizeof(char) * SIGMA_LEN);
        if (get_sval(zsigma, get_sigma(u, c)) == LONG_MASK){
          //set_sval(zsigma, get_sigma(u, c), last[lf[zv]] + 1);
          set_sval(zsigma, get_sigma(u, c), get_last(get_lf(zv)) + 1);
        }
        make_permut(sigma + u*SIGMA_LEN, zsigma);
        //zv = lf[zv];
        zv = get_lf(zv);
      }
    }
  }
  for (c=clast+2; c<ALPH_SIZE; c++){
    dfa[v*ALPH_SIZE + c] = dfa[v*ALPH_SIZE + clast+1];
    /*if (back[v] & (1<<(clast+1))){
      back[v] |= (1<<c);
    }*/
    if (is_back(v, clast+1)){
      set_back(v, c);
    }
  }
  delete[] zsigma;
}

void build_dfa(){
  
  SIGMA_LEN = (ALPH_SIZE + 1) / 2;
  sigma = new char [(total + 1) * SIGMA_LEN];

  int BACK_SIZE;

  if (ALPH_SIZE <= 4){
    back_pack_mode = 0;
    BACK_SIZE = (total + 4) / 4;
  }
  else if (ALPH_SIZE <= 8){
    back_pack_mode = 1;
    BACK_SIZE = (total + 2) / 2;
  }
  else{
    back_pack_mode = 2;
    BACK_SIZE = (total + 1);
  }
  back = new short [BACK_SIZE];
  memset(back, 0, sizeof(short) * BACK_SIZE);

  lf_last = new int [total + 1];
  int i;
  for (i=1; i<=total; i++){
    lf_last[i] = 0;
  }
  memset(sigma, 0xFF, sizeof(char) * (total + 1) * SIGMA_LEN);
  for (i=1; i<ALPH_SIZE; i++){
    dfa[1*ALPH_SIZE + i] = 2;
  }
  
  vqsize = 1;
  while (vqsize < words_num) vqsize <<= 1;
  vert_queue = new int [vqsize];
  vqbeg = 0; vqend = 0;
  
  push_vertex(2);
  set_last(1, -1);
  set_lf(1, 1);
  set_lf(2, 1);

  while (vqbeg != vqend){
    cnt_vertex(vert_queue[vqbeg]);
    vqbeg = (vqbeg + 1) & (vqsize - 1);
  }

  delete[] sigma;
  delete[] back;
  delete[] vert_queue;
  delete[] lf_last;
}

//--------------------------------------------------- ANSWER CALCULATION-----------------------------------------

double * cnt_new;
double * cnt_old;
//double * cnt_impl;

double grate;
//double mrate;


// Writes edgelist to swapfile in binary format and returns the number of edges
int create_swapfile(int vnum){
  int j, h, k, cnum = 0, edgnum = 0;
  _set_fmode(_O_BINARY);
  swapfile = fopen(swapfile_name, "w");
  for (j=1; j<=vnum; j++){
    for (h=0; h<ALPH_SIZE; h++){
      k = dfa[j*ALPH_SIZE + h];
      if (!k) continue;
      edgnum++;
      swap_buffer[cnum++] = j;
      swap_buffer[cnum++] = k;
      if ((cnum & (SWAP_BUFFER_SIZE - 1)) == 0){
        fwrite(swap_buffer, sizeof(int), SWAP_BUFFER_SIZE, swapfile);
        cnum = 0;
      }
    }
  }
  fwrite(swap_buffer, sizeof(int), cnum, swapfile);
  fclose(swapfile);
  _set_fmode(_O_TEXT);

  if (OUTPUT_PROGRESS){
    printf("Swap file created!\n\n");
    fflush(stdout);
  }
  return edgnum;
}


void cnt_algo2(){
  int i, j, k, edgnum;
  char h;
  if (USE_SWAP_FILE){
    edgnum = create_swapfile(total);
    delete[] dfa;
  }
  cnt_old = new double [total+1];
  memset(cnt_old, 0, sizeof(double) * (total + 1));
  if (OUTPUT_PROGRESS){
    printf("old counters allocated\n");
    fflush(stdout);
  }
  cnt_new = new double [total+1];
  memset(cnt_new, 0, sizeof(double) * (total + 1));
  if (OUTPUT_PROGRESS){
    printf("new counters allocated\n");
    fflush(stdout);
  }
  cnt_old[1] = 1;
  double pcomp = 1, ccomp, last_loc_max = 0, last_loc_min = 0;
  double * rates = new double [MAXITER];
  for (i=0; i<MAXITER; i++){
    if (USE_SWAP_FILE){
      
      _set_fmode(_O_BINARY);
      swapfile = fopen(swapfile_name, "r");
      int cnum = 0;
      for (j=0; j<edgnum; j++){
        if (cnum == 0){
          fread(swap_buffer, sizeof(int), SWAP_BUFFER_SIZE, swapfile);
        }
        cnt_new[swap_buffer[cnum + 1]] += cnt_old[swap_buffer[cnum]];
        cnum += 2;
        if (cnum >= SWAP_BUFFER_SIZE) cnum = 0;
      }
      fclose(swapfile);
      _set_fmode(_O_TEXT);

    }
    else{
      for (j=1; j<=total; j++){
        for (h=0; h<ALPH_SIZE; h++){
          k = dfa[j*ALPH_SIZE + h];
          if (!k) continue;
          cnt_new[k] += cnt_old[j];
        }
      }
    }
    ccomp = 0;
    for (j=1; j<=total; j++){
      if (ADD_LOOPS) cnt_new[j] += cnt_old[j];
      ccomp += cnt_new[j];
      cnt_old[j] = cnt_new[j];
      cnt_new[j] = 0;
    }
    rates[i] = ccomp / pcomp;
    // ORACLE HERE
    if (i >= MINITER){
      if ((rates[i-1] >= rates[i-2]) && (rates[i-1] >= rates[i])) last_loc_max = rates[i-1];
      if ((rates[i-1] <= rates[i-2]) && (rates[i-1] <= rates[i])) last_loc_min = rates[i-1];
      if (fabs(rates[i] - rates[i-1]) < delta){
        // Oscillating
        if ((last_loc_max > 0) && (last_loc_min > 0)){
          if (last_loc_max - last_loc_min < delta){
            if (OUTPUT_PROGRESS){
              printf("Oscillating sequence! The number of iterations = %d\n", i);
            }
            grate = rates[i] - (ADD_LOOPS == true);
            return;
          }
        }
        // Monotonic
        else{
          if (OUTPUT_PROGRESS){
            printf("Monotonic sequence! The number of iterations = %d\n", i);
          }
          double q = pow(fabs(rates[i]-rates[i-1]), 1.0 / i);
          double sum = (rates[i] - rates[i-1]) / (1 - q);
          grate = rates[i-1] + sum - (ADD_LOOPS == true);
          return;
        }
      }
    }
    pcomp = ccomp;
  }
  if (OUTPUT_PROGRESS){
    printf("\nNot enough iterations! Current difference is %.20lf\n\n", rates[i-1] - rates[i-2]);
  }
  grate = rates[i-1] - (ADD_LOOPS == true);
}

// Edge list
int * edge1;
int * edge2;
bool have_edge_list;

// Some values to output
int scc_num, nontriv_scc_num, scc_size, scc_edgnum;


int * scc;

void cnt_algo1(){
  double minrate, maxrate, crate, alpha;
  int i, j, iter = 0;
  while (iter < MAXITER){
    iter++;
    if (USE_SWAP_FILE){
      _set_fmode(_O_BINARY);
      swapfile = fopen(swapfile_name, "r");
      int z = 0;
      for (i=0; i<scc_edgnum; i++){
        if ((z & (SWAP_BUFFER_SIZE - 1)) == 0){
          fread(swap_buffer, sizeof(int), SWAP_BUFFER_SIZE, swapfile);
        }
        cnt_new[swap_buffer[z + 1]] += cnt_old[swap_buffer[z]];
        z += 2;
        if (z >= SWAP_BUFFER_SIZE) z = 0;
      }
      fclose(swapfile);
      _set_fmode(_O_TEXT);
    }
    else if (have_edge_list){
      for (i=0; i<scc_edgnum; i++){
        cnt_new[edge2[i]] += cnt_old[edge1[i]];
      }
    }
    else{
      for (i=1; i<=scc_size; i++){
        for (j=0; j<ALPH_SIZE; j++){
          if (dfa[i*ALPH_SIZE + j] > 0){
            cnt_new[dfa[i*ALPH_SIZE + j]] += cnt_old[i];
          }
        }
      }
    }
    minrate = 1e100;
    maxrate = 0;
    for (i=1; i<=scc_size; i++){
      if (ADD_LOOPS) cnt_new[i] += cnt_old[i];
      crate = cnt_new[i] / cnt_old[i];
      if (crate < minrate) minrate = crate;
      if (crate > maxrate) maxrate = crate;
      cnt_old[i] = cnt_new[i];
      cnt_new[i] = 0;
    }
    //printf("\nITERATION %d: %.20lf\n", ++iter, (maxrate+minrate)/2);
    if (maxrate - minrate < 2 * delta){
      alpha = (minrate + maxrate) / 2 - (ADD_LOOPS == true);
      if (alpha > grate) grate = alpha;
      if (OUTPUT_PROGRESS) printf("\n%d iterations used\n\n", iter);
      return;
    }
  }
  if (OUTPUT_PROGRESS) printf("\nNot enough iterations or precision error! %.20lf precision only!\n\n", (maxrate-minrate)/2);
  grate = (minrate + maxrate) / 2 - (ADD_LOOPS == true);
}

// Works for one scc only!
void solve_scc(){
  int i, j;
   
  for (i=1; i<=total; i++){
    if (scc[i] >= 0) continue;
    for (j=0; j<ALPH_SIZE; j++){
      if (scc[dfa[i*ALPH_SIZE + j]] >= 0){
        dfa[-scc[i]*ALPH_SIZE + j] = 0;
      }
      else{
        dfa[-scc[i]*ALPH_SIZE + j] = -scc[dfa[i*ALPH_SIZE + j]];
        scc_edgnum++;
      }
    }
  }
  
  delete[] scc;

  have_edge_list = false;
  
  if (USE_SWAP_FILE){
    create_swapfile(scc_size);
    
    delete[] dfa;
  }

  else if (GEN_EDGE_LIST==1 ||
  (GEN_EDGE_LIST==-1 && sizeof(int)*scc_edgnum < sizeof(double)*scc_size && 2*sizeof(int)*scc_edgnum < sizeof(int)*DFA_SIZE*ALPH_SIZE)){
    
    have_edge_list = true;
    edge1 = new int [scc_edgnum];
    edge2 = new int [scc_edgnum];
    int cnum = 0;
    for (i=1; i<=scc_size; i++){
      for (j=0; j<ALPH_SIZE; j++){
        if (dfa[i*ALPH_SIZE + j] > 0){
          edge1[cnum] = i;
          edge2[cnum++] = dfa[i*ALPH_SIZE + j];
        }
      }
    }

    delete[] dfa;
  }

  cnt_old = new double [scc_size + 1];
  if (OUTPUT_PROGRESS){
    printf("old counters allocated\n");
    fflush(stdout);
  }
  cnt_new = new double [scc_size + 1];
  if (OUTPUT_PROGRESS){
    printf("new counters allocated\n");
    fflush(stdout);
  }
  for (i=1; i<=scc_size; i++){
    cnt_new[i] = 0;
    cnt_old[i] = 1;
  }
  
  if (scc_edgnum == scc_size){
    if (grate == 0) grate = 1;
    return;
  }
  nontriv_scc_num++;
  cnt_algo1();
  if (have_edge_list){
    delete[] edge1;
    delete[] edge2;
  }
}

// TARJAN ALGORITHM

int * mtime;
int * father;
char * nxt_used; // binary encoding here: 15-mask of number of edges done, 16-is being proceeded, 32-used, 64-special

int vert_incycle;

void cnt_vert_incycle(){
  memset(nxt_used, 0, sizeof(char) * (total + 1));
  father[1] = 0;
  nxt_used[1] ^= 32; // used
  int cver = 1, cedge, nver;
  while (cver > 0){
    cedge = nxt_used[cver] & LONG_MASK;
    if (cedge == 0){
      nxt_used[cver] ^= 16; // marked
    }
    if (cedge >= ALPH_SIZE){
      nxt_used[cver] ^= 16; // unmark
      cver = father[cver];
      continue;
    }
    nxt_used[cver]++;
    nver = dfa[cver*ALPH_SIZE + cedge];
    if (!nver) continue;
    if ((nxt_used[nver] & 32) == 0){ // new vertex
      father[nver] = cver;
      nxt_used[nver] ^= 32;
      cver = nver;
    }
    else if (nxt_used[nver] & 16){
      vert_incycle = nver;
    }
  }
}

void dfs2(){
  memset(nxt_used, 0, sizeof(char) * (total + 1));
  memset(mtime, 0, sizeof(int) * (total + 1));
  father[vert_incycle] = 0;
  mtime[vert_incycle] = 1; // Here mtime stores the 
  int ctime = 1, cver = vert_incycle, cedge, nver, pver;
  while (cver > 0){
    cedge = nxt_used[cver] & LONG_MASK;
    if (cedge == 0){
      nxt_used[cver] ^= 16; // is in stack
    }
    else{ // check the son
      pver = dfa[cver*ALPH_SIZE + cedge-1];
      if ((pver > 0) && (father[pver] == cver) && (mtime[pver] < mtime[cver])){
        mtime[cver] = mtime[pver];
        nxt_used[cver] |= 32; // improvement
      }
    }
    if (cedge >= ALPH_SIZE){
      // handle vertex away

      if ((nxt_used[cver] & 32) == 0){ // no improvement
        if (cver != vert_incycle){
          nxt_used[cver] ^= 16; // ouf of stack
        }
        else{
          scc_num++;
        }
      }

      cver = father[cver];
      continue;
    }
    nxt_used[cver]++;
    nver = dfa[cver*ALPH_SIZE + cedge];
    if (!nver) continue;
    if (!mtime[nver]){
      ctime++;
      mtime[nver] = ctime;
      father[nver] = cver;
      cver = nver;
      continue;
    }
    else if ((nxt_used[nver] & 16) && (mtime[nver] < mtime[cver])){
      mtime[cver] = mtime[nver];
      nxt_used[cver] |= 32; // improvement
    }
  }
}


void divide_scc_solve(){
  if (!USE_ORACLE){
    int i;

    father = new int [total + 1];
    nxt_used = new char [total + 1];
    cnt_vert_incycle();

    mtime = new int [total + 1];
    dfs2();
    delete[] mtime;
    delete[] father;

    scc = new int [total + 1];
    memset(scc, 0, sizeof(int) * (total + 1));
    
    nxt_used[vert_incycle] |= 64;
    scc_size = 1;
    for (i=1; i<=total; i++){
      if (nxt_used[i] & 32){
        nxt_used[i] |= 64;
        scc_size++;
      }
    }

    int j = 1;
    for (i=1; i<=total; i++){
      if (nxt_used[i] & 64){
        scc[i] = -j;
        j++;
      }
    }

    delete[] nxt_used;

    if (OUTPUT_PROGRESS){
      printf("The number of non-singleton strongly connected components: %d\n", scc_num);
      fflush(stdout);
    }
    if (scc_num < 2){
      solve_scc();
    }
    if (OUTPUT_PROGRESS){
      printf("The number of non-trivial scc: %d\n", nontriv_scc_num);
      printf("The number of vertices in scc: %d\n", scc_size);
      printf("The number of edges in scc: %d\n", scc_edgnum);
      printf("\n");
      fflush(stdout);
    }
  }
  else{
    cnt_algo2();
  }
}

// DEBUG OUTPUT

void dfs_output(int cv, const string& str){
  if (cv < 0) printf("%s\n", str.c_str());
  int i;
  for (i=0; i<ALPH_SIZE; i++){
    if (dfa[cv*ALPH_SIZE + i]){
      string ns = str;
      ns += 'a'+i;
      dfs_output(dfa[cv*ALPH_SIZE + i], ns);
    }
  }
}


void output_dfa(){
  int i, j;
  printf("\n");
  for (i=1; i<=total; i++){
    printf("Vertex number %d: \n", i);
    for (j=0; j<ALPH_SIZE; j++){
      printf("%d ", dfa[i*ALPH_SIZE + j]);
    }
    printf("\n\n");
  }
}

// END DEBUG OUTPUT

void clear_data(){
  grate = 0;
  //mrate = 0;
  scc_num = 0;
  nontriv_scc_num = 0;
  scc_size = 0;
  scc_edgnum = 0;
  words_num = 0;
  max_words_queue_size = 0;
  if (USE_ORACLE && !USE_SWAP_FILE){
    delete[] dfa;
  }
  if (!USE_ORACLE && !USE_SWAP_FILE && !have_edge_list){
    delete[] dfa;
  }
  delete[] cnt_new;
  delete[] cnt_old;
}

void solve(){
  if (OUTPUT_PROGRESS){
    printf("Calculating answer for test:\n");
    printf("Alphabet size = %d, Root length <= %d\nExponent = %d/%d", ALPH_SIZE, ROOT_LENGTH, beta.num, beta.denum);
    if (beta.p) printf("+");
    printf("\nPrecision = %.20lf\n\n", delta);
  }
  init();

  build_antidictionary();

  if (OUTPUT_ANTIDICTIONARY){
    dfs_output(1, "");
    fflush(stdout);
  }

  if (OUTPUT_PROGRESS){
    printf("Maximal queue size = %I64d\n", max_words_queue_size);
    printf("The number of words = %d\n", words_num);
    printf("The number of vertices = %d\n", total);
    fflush(stdout);
  }

  build_dfa();
  if (OUTPUT_DFA){
    output_dfa();
    fflush(stdout);
  }
  if (OUTPUT_PROGRESS){
    printf("\nDFA built!\n\n");
    fflush(stdout);
  }

  divide_scc_solve();

  printf("%.13lf\n", grate);
  fflush(stdout);
  clear_data();
}

// Parses the file with parameters

void read_ini_file(){
  FILE * inif = fopen("params.ini", "r");
  char str[100], val[100];
  while (fscanf(inif, "%s = %s\n", &str, &val) > 0){
    if (!strcmp(str, "QUEUE_SIZE")){
      if (sscanf(val, "%d", &QUEUE_SIZE) > 0){
        auto_queue_size = false;
      }
    }
    if (!strcmp(str, "DFA_SIZE")){
      if (sscanf(val, "%d", &DFA_SIZE) > 0){
        auto_dfa_size = false;
      }
    }
    if (!strcmp(str, "MAX_ITER")){
      sscanf(val, "%d", &MAXITER);
    }
    if (!strcmp(str, "OUTPUT_PROGRESS")){
      OUTPUT_PROGRESS = (val[0]=='t' || val[0]=='T' || val[0]=='1');
    }
    if (!strcmp(str, "USE_ORACLE")){
      USE_ORACLE = (val[0]=='t' || val[0]=='T' || val[0]=='1');
    }
    if (!strcmp(str, "ADD_LOOPS")){
      ADD_LOOPS = (val[0]=='t' || val[0]=='T' || val[0]=='1');
    }
    if (!strcmp(str, "GEN_EDGE_LIST")){
      if (val[0]=='t' || val[0]=='T' || val[0]=='1') GEN_EDGE_LIST = 1;
      else if (val[0]=='f' || val[0]=='F' || val[0]=='0') GEN_EDGE_LIST = 0;
      else GEN_EDGE_LIST = -1;
    }
    if (!strcmp(str, "USE_SWAP_FILE")){
      USE_SWAP_FILE = (val[0]=='t' || val[0]=='T' || val[0]=='1');
    }
  }
}

int main(int argc, char * argv[]){
  read_ini_file();
  // File IO
  if (argc >= 2){
    freopen(argv[1], "r", stdin);
    if (argc >= 3){
      freopen(argv[2], "w", stdout);
    }
    while (scanf("%d%d", &ALPH_SIZE, &ROOT_LENGTH) > 0){
      if (ALPH_SIZE < 0) break;
      scanf("%d%d%d", &beta.num, &beta.denum, &beta.p);
      scanf("%lf", &delta);
      solve();
    }
  }
  // Or console mode
  else{
    printf("Hello! Working in console mode now...\n");
    while (1){
      printf("Alphabet size: ");
      scanf("%d", &ALPH_SIZE);
      printf("Max length of the root: ");
      scanf("%d", &ROOT_LENGTH);
      printf("Beta numerator: ");
      scanf("%d", &beta.num);
      printf("Beta denominator: ");
      scanf("%d", &beta.denum);
      printf("Is there a +? (0/1): ");
      scanf("%d", &beta.p);
      printf("Delta (exponential form is acceptable): ");
      scanf("%lf", &delta);
      solve();
      printf("\nContinue? (0/1): ");
      int ch;
      scanf("%d", &ch);
      if (!ch) break;
    }
  }
  return 0;
}
